iT邦幫忙

2021 iThome 鐵人賽

DAY 23
0
Software Development

我在刷LeetCode時邂逅了Python系列 第 23

Day 23:1974. Minimum Time to Type Word Using Special Typewriter

  • 分享至 

  • xImage
  •  

今日題目

題目連結:1974. Minimum Time to Type Word Using Special Typewriter
題目主題:String, Greedy


簡單說說 Greedy

Greedy 貪婪法,很常聽見的演算法之一,Greedy 在解問題時,會把問題拆成每個小步前進,過程中的每一步都只會選擇當下的最佳答案,但這每一小步前進最終得到的答案不見得會是問題的最佳解。有些問題是可以得到最佳解的,但不一定每種問題都可以得到最佳解。

假設現在要從 A 走到 D ,用 Greedy 方法來解的話,過程如下圖:

https://ithelp.ithome.com.tw/upload/images/20211007/20141336rOGTUJ4VAa.png

可以看到這樣的過程,每走一步都是選擇當下的最佳路徑,路徑解答會是 2 + 1 + 2 = 5,在這個狀況下是最佳解答,但如果把題目稍微改一下,將上面的 2 改成 4,可能就得不到最佳解答了,如下:

https://ithelp.ithome.com.tw/upload/images/20211007/20141336KNPDzCS1rI.png

這樣子用 Greedy 還是會走紅色的路線,這樣得到的答案就是 2 + 1 + 4 = 7,但實際上以這個狀態最佳解就會是綠色路徑 2 + 4 = 6,這就是 Greedy 可能拿不到最佳解的例子。


題目解說

建議可以看看LeetCode原本的題目說明,這邊是用我的方式說明題目,參考就好。

這是一個 a ~ z 的一個特殊的圓型打字機,下圖是LeetCode上面的範例圖:

https://ithelp.ithome.com.tw/upload/images/20211007/20141336p6tXHhSUNB.png

上面會有一個指針,當指針指到某個英文字母時才能輸入目前指到的英文字母,這個指針最初預設會停在 'a'。

規則是,每一秒只能做一個動作,能操作的動作如下:

  • 將指針順時針或逆時針移動一個字
  • 輸入目前指到的英文字母

題目會給一個 word 字串,目標是用最短秒數打完這組字串,最終回傳這個最短秒數。

約束:

  • 1 <= word.length <= 100
  • word 只會由小寫英文字母組成

範例1

輸入: word = "abc"
輸出: 5
解說: 
打字機的移動過程如下:
- 因為預設停在 'a' , 直接輸入 'a' 花了 1 秒。
- 將指針移動到 'b' 往順時鐘移動一步花了 1 秒。
- 輸入 'b' 花了 1 秒。
- 將指針移動到 'c' 往順時鐘移動一步花了 1 秒。
- 輸入 'c' 花了 1 秒。

範例2

輸入: word = "bza"
輸出: 7
解說:
打字機的移動過程如下:
- 將指針移動到 'b' 往順時鐘移動一步花了 1 秒。
- 輸入 'b' 花了 1 秒。
- 將指針移動到 'z' 往逆時鐘移動兩步花了 2 秒。
- 輸入 'z' 花了 1 秒。
- 將指針移動到 'a' 往順時鐘移動一步花了 1 秒。
- 輸入 'a' 花了 1 秒。

範例3

輸入: word = "zjpc"
輸出: 34
解說:
打字機的移動過程如下:
- 將指針移動到 'z' 往逆時鐘移動一步花了 1 秒。
- 輸入 'z' 花了 1 秒。
- 將指針移動到 'j' 往順時鐘移動花了 10 秒。
- 輸入 'j' 花了 1 秒。
- 將指針移動到 'p' 往順時鐘移動花了 6 秒。
- 輸入 'p' 花了 1 秒。
- 將指針移動到 'c' 往順時鐘移動花了 13 秒。
- 輸入 'c' 花了 1 秒。

建議到這邊先停下來,嘗試自己解解看,若沒有想法可再繼續走下去。


解題的想像

文字描述

  1. 宣告兩個變數:
    • seconds: 紀錄總秒數。
    • nowWord: 紀錄目前指針指到的英文字母。
  2. 跑一個迴圈,走過 word 中每個英文字母:
    • 算出 nowWord 移動到目前字母的移動秒數。
      • 將兩個字母轉成 ASCII 數字,相減的絕對值就是移動秒數
    • 若移動秒數超過 26/2 字母的一半,代表往另一個方向移動會比較快,反方向移動秒數的計算方式用 26個字母 - 移動秒數就可以得到。 Ex. a 移到 o = 14,反方向就會是 26 - 14 = 12,秒數會比較短。
    • 移動到目前的字母後,將移動秒數 + 輸入的 1 秒再加進 seconds,並將 nowWord 指定到目前的字母上。
  3. 最終回傳 seconds 總秒數。

圖解過程

範例:word = "fuc"

下圖是第一個步驟,中間的指針預設在 'a' 字母上面,移動綠色路線到 'f' 花了 5 秒鐘,加 1 是因為還要輸入花 1 秒鐘,而中間的seconds會將目前花的秒數加總起來。

https://ithelp.ithome.com.tw/upload/images/20211007/20141336S2mm5SYIxt.png

接著上個步驟指針停在 'f' 上面,移到 'u',走紅色路線 15 秒,超過 26 / 2 的 13,因此往反方向走綠色路線,26 - 15 = 11,加上輸入要花的 1 秒鐘,之後 seconds 再加上目前的秒數。

https://ithelp.ithome.com.tw/upload/images/20211007/201413366j0Cz7BwHc.png

繼續從 'u' 移到 'c',走紅色路線 18 秒,超過 26 / 2 的 13,往反方向走綠色路線,26 - 18 = 8,加上輸入要花的 1 秒鐘,之後 seconds 再加上目前的秒數得到總秒數 27。
https://ithelp.ithome.com.tw/upload/images/20211007/20141336lOZpVEkJek.png

最終這個範例會回傳總秒數 27 秒。

若因為沒想法而走到這邊,建議看完想像以後再給自己一次機會試一次。


程式碼撰寫

class Solution:
    def minTimeToType(self, word: str) -> int:
        # 紀錄花費秒數
        seconds = 0
        # 紀錄目前指針指導的英文字母
        nowWord = 'a'
        # 將 word 中每個字走一次
        for idx in range(len(word)):
            # 算出需移動的秒數
            moveSeconds = abs(ord(word[idx]) - ord(nowWord))
            # 若超過一半代表往反方向走比較快
            # 26個英文字母 - 移動秒數 = 反方向的移動秒數
            if moveSeconds > (26/2):
                moveSeconds = 26 - moveSeconds
            # 每次找到一個字除了移動秒數以外,+1 是輸入秒數
            seconds += (moveSeconds + 1)
            # 將指針指定到目前的英文字母上
            nowWord = word[idx]
        return seconds

希望您今天能瞭解到...

  1. Greedy 的基本概念
  2. 1974.Minimum Time to Type Word Using Special Typewriter 的解題方法

若內容有什麼問題或建議歡迎一起交流:)
感謝您今天願意花時間看完這篇文章~~~~

Next:605. Can Place Flowers


上一篇
Day 22:1863. Sum of All Subset XOR Totals
下一篇
Day 24:605. Can Place Flowers
系列文
我在刷LeetCode時邂逅了Python30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言